The exhaust gas of diesel engines, gasoline engines, and other internal combustion engines includes, for example, carbon monoxide (CO), unburned fuel (HC), nitrogen oxides (NOX), particulate matter (PM), and other constituents. The internal combustion engines are mounted with exhaust purification systems for removing these constituents. As one method which removes nitrogen oxides, it is known to arrange an NOX storage catalyst in the engine exhaust passage. Japanese Patent Publication (A) No. 2010-48134 discloses an exhaust purification system which arranges a plurality of NOX storage catalysts in the exhaust passage and provides fuel feeding means for feeding fuel to the respective NOX storage catalysts. It is disclosed to feed fuel from the fuel feeding means to the respectively corresponding NOX storage catalysts when the NOX storage catalysts should be made to release the stored NOX for reduction. Further, this publication discloses to set fuel feed amounts from the plurality of fuel feeding means so that the total value of fuel feed amounts from the fuel feeding means substantially matches a target value. Furthermore, it discloses to use the set feed amounts and the temperatures of the NOX storage catalysts as the basis to calculate the NOX purification rates of the NOX storage catalysts and to set the fuel feed amounts from the fuel feeding means so that the total value of the NOX purification rates exceeds an allowable value.